package com.seatiger.structure.trie;

import java.util.TreeMap;

/**
 * https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/
 */
public class LC_211 {
    static class WordDictionary {
        private class Node {
            private boolean isWord;
            private TreeMap<Character, Node> next;
            public Node(boolean isWord) {
                this.isWord = isWord;
                this.next = new TreeMap<>();
            }
            public Node() {
                this(false);
            }
        }
        private Node root;
        public WordDictionary() {
            this.root = new Node();
        }

        public void addWord(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.next.get(c) == null){
                    cur.next.put(c,new Node());
                }
                cur = cur.next.get(c);
            }
            cur.isWord = true;
        }

        public boolean search(String word) {
            return match(root,word,0);
        }

        private boolean match(Node node,String word,int index) {
            if (word.length() == index) {
                return node.isWord;
            }
            char c = word.charAt(index);
            if ( c != '.') {
                if (node.next.get(c) == null) {
                    return false;
                }
                return match(node.next.get(c),word,index+1);
            }else {
                for (char nextChar : node.next.keySet()){
                    if (match(node.next.get(nextChar), word,index+1)) {
                        return true;
                    }
                }
                return false;
            }
        }
    }

    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        wordDictionary.search("pad"); // return False
        wordDictionary.search("bad"); // return True
        wordDictionary.search(".ad"); // return True
        wordDictionary.search("b.."); // return True
    }
}
